README.md

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 

Follow up: Recursive solution is trivial, could you do it iteratively?

Solutions (Python)

1. Recursion

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: definorderTraversal(self, root: TreeNode) ->List[int]: ifnotroot: return [] returnself.inorderTraversal(root.left) + \ [root.val] +self.inorderTraversal(root.right)

2. Iteration

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: definorderTraversal(self, root: TreeNode) ->List[int]: vals= [] nodes= [] node=rootwhilenodeornodes: whilenode: nodes.append(node) node=node.leftnode=nodes.pop() vals.append(node.val) node=node.rightreturnvals

Solutions (Rust)

1. Recursion

// Definition for a binary tree node.// #[derive(Debug, PartialEq, Eq)]// pub struct TreeNode {// pub val: i32,// pub left: Option<Rc<RefCell<TreeNode>>>,// pub right: Option<Rc<RefCell<TreeNode>>>,// }// // impl TreeNode {// #[inline]// pub fn new(val: i32) -> Self {// TreeNode {// val,// left: None,// right: None// }// }// }use std::rc::Rc;use std::cell::RefCell;implSolution{pubfninorder_traversal(root:Option<Rc<RefCell<TreeNode>>>) -> Vec<i32>{letmut vals = Vec::new();ifletSome(n) = root { vals.append(&mutSelf::inorder_traversal(n.borrow().left.clone())); vals.push(n.borrow().val); vals.append(&mutSelf::inorder_traversal(n.borrow().right.clone()));} vals }}

2. Iteration

// Definition for a binary tree node.// #[derive(Debug, PartialEq, Eq)]// pub struct TreeNode {// pub val: i32,// pub left: Option<Rc<RefCell<TreeNode>>>,// pub right: Option<Rc<RefCell<TreeNode>>>,// }// // impl TreeNode {// #[inline]// pub fn new(val: i32) -> Self {// TreeNode {// val,// left: None,// right: None// }// }// }use std::rc::Rc;use std::cell::RefCell;implSolution{pubfninorder_traversal(root:Option<Rc<RefCell<TreeNode>>>) -> Vec<i32>{letmut vals = Vec::new();letmut nodes = Vec::new();letmut cur = root.clone();while !nodes.is_empty() || cur.is_some(){whileletSome(n) = cur { nodes.push(n.clone()); cur = n.borrow().left.clone();} cur = nodes.pop();ifletSome(n) = cur { vals.push(n.borrow().val); cur = n.borrow().right.clone();}} vals }}